package com.demo.java.OD651_700.OD665;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【小明减肥(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/148081741
 */
public class OdMain {
    /**
     * 深度优先搜索辅助函数
     * @param start 当前考虑的运动索引
     * @param remainingK 还需要选择的运动数量
     * @param currentSum 当前已选运动的卡路里和
     * @param n 运动总数
     * @param t 目标卡路里和
     * @param calories 卡路里数组
     * @return 满足条件的组合数量
     */
    private int dfs(int start, int remainingK, int currentSum,
                    int n, int t, int[] calories) {
        // 基础情况：已经选够k个运动
        if (remainingK == 0) {
            return currentSum == t ? 1 : 0;
        }

        // 如果剩余的运动不够选或者已经超出目标值，返回0
        if (start >= n || remainingK > n - start || currentSum > t) {
            return 0;
        }

        // 不选择当前运动
        int count = dfs(start + 1, remainingK, currentSum, n, t, calories);

        // 选择当前运动
        count += dfs(start + 1, remainingK - 1, currentSum + calories[start], n, t, calories);

        return count;
    }

    /**
     * 计算满足条件的运动组合数量
     * @param n 运动总数
     * @param t 目标卡路里和
     * @param k 需要选择的运动数量
     * @param calories 每个运动的卡路里向量
     * @return 满足条件的组合数量
     */
    public int countExerciseCombinations(int n, int t, int k, int[] calories) {
        // 输入验证
        if (!(0 < n && n < 10 && t > 0 && 0 < k && k <= n)) {
            return 0;
        }

        return dfs(0, k, 0, n, t, calories);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int n = scanner.nextInt();
        int t = scanner.nextInt();
        int k = scanner.nextInt();

        int[] calories = new int[n];
        for (int i = 0; i < n; i++) {
            calories[i] = scanner.nextInt();
        }

        OdMain solution = new OdMain();
        // 输出结果
        System.out.println(solution.countExerciseCombinations(n, t, k, calories));
    }
}